package com.example.spring5.ms;

import com.fasterxml.jackson.databind.util.LinkedNode;
import org.w3c.dom.Node;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**
 * Google的一道面试题：
 * Design an LRU cache with all the operations to be done in O(1)O(1) .
 * @Author: Hu Rui
 * @Date: 2021/11/10 23:18
 */
public class LRUCache {
    private int capacity;
    private Map<String, CacheObject> cacheMap;
    private LinkedList<String> keyLinkedList = new LinkedList();

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cacheMap = new HashMap<>((int) (capacity / 0.75f + 1));
    }

    public void add(String key, String val) {
        CacheObject cacheObject = new CacheObject(key, val);
        if (keyLinkedList.size() >= capacity) {
            String lastElement = keyLinkedList.removeLast();
            cacheMap.remove(lastElement);
        }
        keyLinkedList.addFirst(key);
        cacheMap.put(key, cacheObject);
    }

    private void setHead(CacheObject cacheObject) {
        String key = keyLinkedList.removeLast();
        keyLinkedList.addFirst(key);
    }

    public String find(String key) {
        CacheObject cacheObject = cacheMap.get(key);
        if (cacheObject != null) {
            setHead(cacheObject);
        }
        return cacheObject.getVal();
    }


}
